package leetcode_500;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

/**
 * MinimumGeneticMutation_433_ 寻找最短基因变异的步数  每次只能变异一个基因 且变异的基因必须在给定基因库中
 * 2018年8月16日 下午4:49:19
 * @author 周杨
 * describe :用广度优先遍历 每次遍历一个基因 用队列装载目前合法变异基因 AC 70%
 *
 */
public class MinimumGeneticMutation_433_ {
	
	public int minMutation(String start, String end, String[] bank) {
		   //边界用例
	       if (start==null || end==null || start.length()!=end.length()) return -1;
	        int steps = 0;
	        char[] mutations = new char[]{'A', 'C', 'G', 'T'};
	        HashSet<String> validGene = new HashSet<String>();
	        for (String str : bank) {
	            validGene.add(str);
	        }
	        if (!validGene.contains(end)) return -1;
	        
	        if (validGene.contains(start)) validGene.remove(start);//避免死循环
	        Queue<String> q = new LinkedList<String>();
	        q.offer(start);
	        while (!q.isEmpty()) {
	            int size = q.size();
	            for (int k=0; k<size; k++) {//遍历此时队列里每个合法的基因序列 保证他们在一个层里面
	                String cur = q.poll();
	                for (int i=0; i<cur.length(); i++) {
	                    for (char c : mutations) {//每次换一个字母ATCG 看能否进入合法库
	                        StringBuilder ss = new StringBuilder(cur);
	                        ss.setCharAt(i, c);
	                        String afterMutation = ss.toString();
	                        if (afterMutation.equals(end)) return steps+1;//最先变的一定是最短步数的
	                        if (validGene.contains(afterMutation)) {
	                            validGene.remove(afterMutation);//避免死循环
	                            q.offer(afterMutation);
	                        }
	                    }
	                }
	            }
	            steps++;
	        }
	        return -1;
	    }
}
